带分数
题目 带分数
思路分析
问题逐渐简化 变成了先求1~9的全排列 再把每一个排列想办法分成abc三个部分 若abc三部分加起来能等于输入的数 就成立
另外需要注意除法丢失精度问题 变成乘法
求全排列 就可以用前面得到的两种方法了 dfs或者next_permutation
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int x,res;
int calc(int l,int r){
int ans=0;
for(int i=l;i<=r;i++)
ans=ans*10+path[i];
return ans;
}
void dfs(int u){
if(u==10){
for(int i=1;i<=7;i++){
for(int j=i+1;j<=8;j++){
int a=calc(1,i);
int b=calc(i+1,j);
int c=calc(j+1,9);
if(a*c+b==c*x)
res++;
}
}
return;
}
for(int i=1;i<=9;i++){
if(!st[i]){
st[i]=true;
path[u]=i;
dfs(u+1);
path[u]=0;
st[i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>x;
dfs(1);
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> alls={1,2,3,4,5,6,7,8,9};
int x,res;
int calc(int l,int r){
int ans=0;
for(int i=l;i<=r;i++)
ans=ans*10+alls[i];
return ans;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>x;
do{
for(int i=0;i<=6;i++){
for(int j=i+1;j<=7;j++){
int a=calc(0,i);
int b=calc(i+1,j);
int c=calc(j+1,8);
if(a*c+b==c*x)
res++;
}
}
}while(next_permutation(alls.begin(),alls.end()));
cout<<res;
return 0;
}
💬 评论